// Package compiler:编译器包
package compiler

import (
	"fmt"
	"sort"
	"z-lang/ast"
	"z-lang/code"
	"z-lang/object"
)

// EmittedInstruction 指令追踪器 - 记录指令的操作码及其在指令集合中的位置
type EmittedInstruction struct {
	Opcode   code.Opcode // 操作码
	Position int         // 位置
}

// CompilationScope 编译作用域
type CompilationScope struct {
	instruction         code.Instructions  // 字节码指令 - 包含字节码操作码，字节码操作数. 操作码一般是一个字节，操作数可能有多个
	lastInstruction     EmittedInstruction // 最后一条指令的追踪信息
	previousInstruction EmittedInstruction // 倒数第二条指令的追踪信息
}

// Compiler 编译器结构体
//  1. 递归遍历 ast.Node 抽象语法树
//  2. 将 抽象语法树 上的节点 ast.Node 转为 字面量对象(如: ast.IntegerLiteral, ast.Boolean ... )
//  3. 对 字面量对象 (如: ast.IntegerLiteral, ast.Boolean ... ) 进行求值, 得到 实际对象 object.Object
//  4. 将 实际对象 object.Object 存入到 常量池 Compiler.constants，然后根据 对象存储的位置，编写出 指令 code.Instructions
type Compiler struct {
	constants   []object.Object    // 常量池
	symbolTable *SymbolTable       // 符号表 - 符号即变量名, ...
	scopes      []CompilationScope // 编译作用域
	scopeIdx    int                // 编译作用域索引下标
}

// New 创建一个编译器
func New() *Compiler {

	cs := CompilationScope{
		instruction:         code.Instructions{},
		lastInstruction:     EmittedInstruction{},
		previousInstruction: EmittedInstruction{},
	}

	symbolTable := NewSymbolTable()
	for i, v := range object.Builtings {
		symbolTable.DefineBuiltin(i, v.Name)
	}

	return &Compiler{
		constants:   []object.Object{},
		symbolTable: symbolTable,
		scopes:      []CompilationScope{cs},
		scopeIdx:    0,
	}
}

// NewWithState 创建一个编译器，并且保存之前的状态信息
func NewWithState(s *SymbolTable, constants []object.Object) *Compiler {
	c := New()
	c.symbolTable = s
	c.constants = constants
	return c
}

// Compile 编译.
//  1. 遍历抽象语法树, 将 抽象语法树的节点 ast.Node 转换成 对应的字面量(如: ast.IntegerLiteral )
//  2. 对字面量进行求值, 得到对象 object.Object (如: object.Integer )
//  3. 将对象存储到常量池中， 根据对象存储在常量池中的位置，编写出对应的 字节码指令
func (c *Compiler) Compile(node ast.Node) error {
	switch node := node.(type) {
	case *ast.Program:
		for _, s := range node.Statements {
			err := c.Compile(s)
			if err != nil {
				return err
			}
		}

	case *ast.ExpressionStatement:
		err := c.Compile(node.Expression)
		if err != nil {
			return err
		}
		c.emit(code.OpPop)

	case *ast.PrefixExpression:
		err := c.compilePrefixExpression(node)
		if err != nil {
			return err
		}

	case *ast.InfixExpression:
		// 将 小于 运算 重排序优化成 大于 运算
		// 即 先编译 right 再 编译 left
		if node.Operator == "<" {
			err := c.Compile(node.Right)
			if err != nil {
				return err
			}

			err = c.Compile(node.Left)
			if err != nil {
				return err
			}

			c.emit(code.OpGreaterThan)
			return nil
		}

		err := c.compileInfixExpression(node)
		if err != nil {
			return err
		}

	case *ast.IntegerLiteral:
		integer := &object.Integer{Value: node.Value}
		c.emit(code.OpConstant, c.addConstant(integer))

	case *ast.Boolean:
		if node.Value {
			c.emit(code.OpTrue)
		} else {
			c.emit(code.OpFalse)
		}

	case *ast.IFExpression: // if 语句
		// 编译条件
		err := c.Compile(node.Condition)
		if err != nil {
			return err
		}
		// 逻辑跳转 - 非真跳转操作码 - 在虚拟机栈顶部内容不为真或者为空的时候进行跳转
		// 这里还少了一个跳转偏移量的操作数，这个需要编译完条件分支之后，再进行回填，现在只是做个占位
		jumpNotTruthyPos := c.emit(code.OpJumpNotTruthy)
		// if condition 为true的分支
		err = c.Compile(node.Consequence)
		if err != nil {
			return err
		}

		// 如果最后一条语句是 code.OpPop 那么 我们需要移除它
		// 移除是考虑到 编译时是走的 ast.ExpressionStatement 编译到最后会填入一个 OpPop 的指令，
		// 而在 let r = if (a > b) { 10 } else { 20 } 这种情况下 我们应该要保留一个值赋给 r，不能用 OpPop 指令将结果弹栈
		if c.lastInstructionIs(code.OpPop) {
			c.removeLastPop()
		}
		// 这里还少了一个跳转偏移量的操作数，这个需要编译完条件分支之后，再进行回填，现在只是做个占位
		jumpPos := c.emit(code.OpJump)
		// 条件分支编译后的长度
		afterConsequencePos := len(c.currentInstruction())
		// 对非真跳转操作码进行回填
		c.changeOperand(jumpNotTruthyPos, afterConsequencePos)
		// 如果没有 else 分支，那么直接对 逻辑跳转 - 非真跳转操作码 进行操作数回填
		if node.Alternative == nil {
			c.emit(code.OpNull)
		} else {
			err = c.Compile(node.Alternative)
			if err != nil {
				return err
			}

			// 如果最后一条语句是 code.OpPop 那么 我们需要移除它
			// 移除是考虑到 编译时是走的 ast.ExpressionStatement 编译到最后会填入一个 OpPop 的指令，
			// 而在 let r = if (a > b) { 10 } else { 20 } 这种情况下 我们应该要保留一个值赋给 r，不能用 OpPop 指令将结果弹栈
			if c.lastInstructionIs(code.OpPop) {
				c.removeLastPop()
			}
		}
		// 对无条件跳转操作码进行回填
		afterAlternativePos := len(c.currentInstruction())
		c.changeOperand(jumpPos, afterAlternativePos)

	case *ast.BlockStatement: // 表达式
		for _, s := range node.Statements {
			err := c.Compile(s)
			if err != nil {
				return err
			}
		}

	case *ast.LetStatement: // let 变量定义表达式
		// 在编译函数体之前，在符号表中定义函数即将被绑定的名称，从而允许函数体引用此函数名
		symbol := c.symbolTable.Define(node.Name.Value)
		err := c.Compile(node.Value)
		if err != nil {
			return err
		}

		if symbol.Scope == GlobalScope {
			c.emit(code.OpSetGlobal, symbol.Index)
		} else {
			c.emit(code.OpSetLocal, symbol.Index)
		}

	case *ast.Identifier: // 变量
		symbol, ok := c.symbolTable.Resolve(node.Value)
		if !ok {
			return fmt.Errorf("undefined variable %s", node.Value)
		}
		c.loadSymbol(symbol)

	case *ast.StringLiteral: // 字符串字面量编译
		str := &object.String{Value: node.Value}
		c.emit(code.OpConstant, c.addConstant(str))

	case *ast.ArrayLiteral: // 数组字面量编译
		for _, e := range node.Elements {
			err := c.Compile(e)
			if err != nil {
				return err
			}
		}
		c.emit(code.OpArray, len(node.Elements))

	case *ast.HashLiteral: // 哈希表字面量编译
		// 这里需要先将哈希表的 key 取出来进行排序，因为Go在遍历映射的键和值时不能保证一致的顺序
		//如果不这样做，那么编译的键值对的排列顺序和代码中定义的顺序将会有一定出入
		var keys []ast.Expression
		for k := range node.Pairs {
			keys = append(keys, k)
		}
		sort.Slice(keys, func(i, j int) bool {
			return keys[i].String() < keys[j].String()
		})

		for _, k := range keys {
			err := c.Compile(k)
			if err != nil {
				return err
			}
			err = c.Compile(node.Pairs[k])
			if err != nil {
				return err
			}
		}
		c.emit(code.OpHash, len(node.Pairs)*2)

	case *ast.IndexExpression: // 索引表达式
		err := c.Compile(node.Left)
		if err != nil {
			return err
		}
		err = c.Compile(node.Index)
		if err != nil {
			return err
		}
		c.emit(code.OpIndex)

	case *ast.FunctionLiteral: // 处理函数字面量
		// 在编译函数的时候更改指令的存储位置
		//   1. 在遇见 ast.FunctionLiteral 时 通过调用 enterScope() 进入一个全新的作用域
		//   2. 然后在这个全新的作用域编译 node.Body，将函数的主体内容编译成字节码
		//   3. 函数编译完成之后，通过调用 c.enterScope() 退出这个编译函数的作用域，并取出函数编译后的字节码指令
		//   4. 根据 取出的字节码指令 创建出 object.CompiledFunction 对象来保存这些字节码指令
		//   5. 将这个 object.CompiledFunction 对象 存入到常量池中去
		c.enterScope()

		if node.Name != "" {
			c.symbolTable.DefineFunctionName(node.Name)
		}

		for _, p := range node.Parameters {
			c.symbolTable.Define(p.Value)
		}

		err := c.Compile(node.Body)
		if err != nil {
			return err
		}

		if c.lastInstructionIs(code.OpPop) {
			c.replaceLastPopWithReturn()
		}
		if !c.lastInstructionIs(code.OpReturnValue) {
			c.emit(code.OpReturn)
		}

		freeSymbols := c.symbolTable.FreeSymbols
		numDefinition := c.symbolTable.numDefinition
		instructions := c.leaveScope()

		for _, s := range freeSymbols {
			c.loadSymbol(s)
		}

		compiledFunc := &object.CompiledFunction{Instructions: instructions, NumLocals: numDefinition, NumParameters: len(node.Parameters)}
		cfIdx := c.addConstant(compiledFunc)
		c.emit(code.OpClosure, cfIdx, len(freeSymbols))

	case *ast.ReturnStatement: // return语句
		err := c.Compile(node.ReturnValue)
		if err != nil {
			return err
		}
		c.emit(code.OpReturnValue)

	case *ast.CallExpression: // 方法/函数 调用表达式
		err := c.Compile(node.Function)
		if err != nil {
			return err
		}
		for _, a := range node.Arguments {
			err = c.Compile(a)
			if err != nil {
				return err
			}
		}
		c.emit(code.OpCall, len(node.Arguments))
	}
	return nil
}

// replaceLastPopWithReturn 将最后一条指令替换成 OpReturnValue 指令
func (c *Compiler) replaceLastPopWithReturn() {
	lastPos := c.scopes[c.scopeIdx].lastInstruction.Position
	c.replaceInstruction(lastPos, code.Make(code.OpReturnValue))

	c.scopes[c.scopeIdx].lastInstruction.Opcode = code.OpReturnValue
}

// changeOperand 替换指令的操作数. 本质上来说是，构建一个全新的指令，然后将旧的指令替换掉
func (c *Compiler) changeOperand(opPos int, operand int) {
	op := code.Opcode(c.currentInstruction()[opPos])
	newInstruction := code.Make(op, operand)

	c.replaceInstruction(opPos, newInstruction)
}

// replaceInstruction 替换指令
func (c *Compiler) replaceInstruction(pos int, newInstruction []byte) {

	ins := c.currentInstruction()

	for i := 0; i < len(newInstruction); i++ {
		ins[pos+i] = newInstruction[i]
	}
}

// removeLastPop 移除指令集合中的最后一条指令
func (c *Compiler) removeLastPop() {
	//c.instructions = c.instructions[:c.lastInstruction.Position]
	//c.lastInstruction = c.previousInstruction
	last := c.scopes[c.scopeIdx].lastInstruction
	prev := c.scopes[c.scopeIdx].previousInstruction

	old := c.currentInstruction()
	newInstruction := old[:last.Position]

	c.scopes[c.scopeIdx].instruction = newInstruction
	c.scopes[c.scopeIdx].lastInstruction = prev
}

// lastInstructionIs 最后一条语句是否为 传入的op. true 表示是，false 表示不是
func (c *Compiler) lastInstructionIs(op code.Opcode) bool {
	if len(c.currentInstruction()) == 0 {
		return false
	}
	return c.scopes[c.scopeIdx].lastInstruction.Opcode == op
}

// compilePrefixExpression 编译 前缀表达式
func (c *Compiler) compilePrefixExpression(node *ast.PrefixExpression) error {
	err := c.Compile(node.Right)
	if err != nil {
		return err
	}
	switch node.Operator {
	case "!":
		c.emit(code.OpBang)
	case "-":
		c.emit(code.OpMinus)
	case "~":
		c.emit(code.OpNot)
	default:
		return fmt.Errorf("compiler unsupport operator: %s", node.Operator)
	}
	return nil
}

// compileInfixExpression 编译 中缀表达式
func (c *Compiler) compileInfixExpression(node *ast.InfixExpression) error {
	err := c.Compile(node.Left)
	if err != nil {
		return err
	}
	err = c.Compile(node.Right)
	if err != nil {
		return err
	}
	switch node.Operator {
	case "+":
		c.emit(code.OpAdd)
	case "-":
		c.emit(code.OpSub)
	case "*":
		c.emit(code.OpMul)
	case "/":
		c.emit(code.OpDiv)
	case ">":
		c.emit(code.OpGreaterThan)
	case "==":
		c.emit(code.OpEqual)
	case "!=":
		c.emit(code.OpNotEqual)
	case "&":
		c.emit(code.OpAnd)
	case "|":
		c.emit(code.OpOr)
	case "^":
		c.emit(code.OpXor)
	case "<<":
		c.emit(code.OpLShift)
	case ">>":
		c.emit(code.OpRShift)
	case ">>>":
		c.emit(code.OpURShift)
	case "&&":
		c.emit(code.OpLogicAnd)
	case "||":
		c.emit(code.OpLogicOr)
	default:
		return fmt.Errorf("unknown operator %s", node.Operator)
	}
	return nil
}

// addConstant 往常量池中添加常量，并返回常量的存储下标
func (c *Compiler) addConstant(obj object.Object) int {
	c.constants = append(c.constants, obj)
	return len(c.constants) - 1
}

// emit 根据 操作码 和 操作数 创建 指令，并将 指令 添加到 编译器 的指令集合中，然后返回 该指令 在指令集合中的存储下标
func (c *Compiler) emit(op code.Opcode, operands ...int) int {
	ins := code.Make(op, operands...)
	pos := c.addInstruction(ins)

	c.setLastInstruction(op, pos)

	return pos
}

// setLastInstruction 设置最后一条指令追踪信息
func (c *Compiler) setLastInstruction(opcode code.Opcode, position int) {
	previous := c.scopes[c.scopeIdx].lastInstruction
	last := EmittedInstruction{Opcode: opcode, Position: position}

	c.scopes[c.scopeIdx].previousInstruction = previous
	c.scopes[c.scopeIdx].lastInstruction = last
}

// addInstruction 往指令集合中添加新的指令，并返回新指令在指令池中的存储下标
func (c *Compiler) addInstruction(ins code.Instructions) int {
	posNewInstruction := len(c.currentInstruction())
	updatedInstruction := append(c.currentInstruction(), ins...)

	c.scopes[c.scopeIdx].instruction = updatedInstruction

	return posNewInstruction
}

// currentInstruction 获取当前编译作用域内的当前指令
func (c *Compiler) currentInstruction() code.Instructions {
	return c.scopes[c.scopeIdx].instruction
}

// loadSymbol 加载符号信息
func (c *Compiler) loadSymbol(s Symbol) {
	switch s.Scope {
	case GlobalScope:
		c.emit(code.OpGetGlobal, s.Index)
	case LocalScope:
		c.emit(code.OpGetLocal, s.Index)
	case BuiltinScope:
		c.emit(code.OpGetBuiltin, s.Index)
	case FreeScope:
		c.emit(code.OpGetFree, s.Index)
	case FunctionScope:
		c.emit(code.OpCurrentClosure)
	}
}

// enterScope 添加编译作用域，并进入这个编译作用域(即 scopeIdx ++)
func (c *Compiler) enterScope() {
	scope := CompilationScope{
		instruction:         code.Instructions{},
		lastInstruction:     EmittedInstruction{},
		previousInstruction: EmittedInstruction{},
	}
	c.scopes = append(c.scopes, scope)
	c.scopeIdx++

	c.symbolTable = NewEnclosedSymbolTable(c.symbolTable)
}

// leaveScope 删除编译作用域，并离开编译作用域(即 scopeIdx --), 同时返回当前指令
func (c *Compiler) leaveScope() code.Instructions {
	curInstruction := c.currentInstruction()

	c.scopes = c.scopes[:len(c.scopes)-1]
	c.scopeIdx--

	c.symbolTable = c.symbolTable.Outer

	return curInstruction
}

// Bytecode 构建 Bytecode 字节码信息结构
func (c *Compiler) Bytecode() *Bytecode {
	return &Bytecode{
		Instructions: c.currentInstruction(),
		Constants:    c.constants,
	}
}

// Bytecode 字节码信息结构体
//
//	包含编译器生成的Instruction 和 编译器求值的Constants
//	主要是传输给虚拟机并在编译器测试中做断言的内容
type Bytecode struct {
	Instructions code.Instructions // 指令
	Constants    []object.Object   // 常量池
}
